Although nearly 20 years have passed since its conception, the feasibility pump algorithm remains a widely used heuristic to find feasible primal solutions to mixed-integer linear problems. Many extensions of the initial algorithm have been proposed. Yet, its core algorithm remains centered around two key steps: solving the linear relaxation of the original problem to obtain a solution that respects the constraints, and rounding it to obtain an integer solution. This paper shows that the traditional feasibility pump and many of its follow-ups can be seen as gradient-descent algorithms with specific parameters. A central aspect of this reinterpretation is observing that the traditional algorithm differentiates the solution of the linear relaxation with respect to its cost. This reinterpretation opens many opportunities for improving the performance of the original algorithm. We study how to modify the gradient-update step as well as extending its loss function. We perform extensive experiments on MIPLIB instances and show that these modifications can substantially reduce the number of iterations needed to find a solution.

Since MIP linear problems include both continuous and integer variables, they are proved to belong to the NP-hard class (see [38] for a more detailed analysis), meaning that they are not solvable in polynomial time. The complete exploration of the integer feasible set, whose cardinality grows exponentially with the number of variables, is yet possible to achieve the optimal solution, but for most of the practically significant instances, it would require unacceptable computational effort. In fact, the only way to solve to optimality any mixed-integer problem is to apply some of the well-known Branch and Bound techniques. However, despite combinatorial optimization community provided a great deal of these algorithms, for which the reader should refer to [31, 34, 16], MIP problems complexity is inherent with their belonging to NP-hard class. Therefore, when tackling MIP problems, one either seeks particular structures allowing to bring down the complexity, such as the availability, for a given class of problems, of the optimal formulation or exploits cutting plane generation to dramatically reduce the feasible region dimension. However, we often encounter MIP problems without having any prior knowledge of possible structures and, thus, pursuing the globally optimal solution could be in practice impossible or inefficient, since for our purpose a sub-optimal approximation is considered to be good enough. This makes heuristics one of the most widespread and feasible ways to achieve sub-optimal solutions of MIP problems within an affordable computational time. For the purpose of highlighting the perspective of our research, we can define two classes of MIP heuristics: improvement heuristics and start heuristics.